//
// Created by PC on 2017/12/20.
//

#ifndef GRAPHREPRESENTATION_SPARSEGRAPH_H
#define GRAPHREPRESENTATION_SPARSEGRAPH_H

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
/**
 * 稀疏图 邻接表
 */
class SparseGraph{
private:
    int n,m;
    bool directed;
    vector<vector<int>> g;
public:
    const vector<vector<int>> &getG() const {
        return g;
    }

    SparseGraph(int n, bool directed){
        this->n=n;
        this->m=0;
        this->directed=directed;
        g=vector<vector<int>>(n,vector<int>());
    }
    ~SparseGraph(){}
    int V(){ return n; }
    int E(){ return m; }

    void addEdge(int v, int w) {
        assert(v>=0&&v<n);
        assert(w>=0&&w<n);
        //排除自环边
        //排除平行边
        if(hasEdge(v,w)||v==w)
            return;
        g[v].push_back(w);
        if(v!=w&& !directed)
            g[w].push_back(v);
        m++;
    }
    // 验证图中是否有从v到w的边
    bool hasEdge( int v , int w ){

        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );

        for( int i = 0 ; i < g[v].size() ; i ++ )
            if( g[v][i] == w )
                return true;
        return false;
    }


};
#endif //GRAPHREPRESENTATION_SPARSEGRAPH_H
